1. Field of the Invention
This invention relates to an automatic placement method by which logic cells are arranged efficiently on a semiconductor substrate.
2. Description of the Prior Art
FIG. 1 shows a schematic diagram of gate array formed on a semiconductor substrate such as a chip 61. In the same diagram, a plurality of basic cells 63 are arranged in matrix (a basic cell array) on the semiconductor chip 61. I/O cells 65 are placed around the basic cells 63.
Each basic cell 63 includes a predetermined number of transistors. Any logic circuit such as an inverter or a NAND circuit can be formed by wiring among the basic cells.
Many kinds of these logic circuits or logic cells (usually called macro cells), obtained by the method mentioned above, are stored in a library.
In order to make a LSI circuit, some required macro cells stored in the library are selected and placed automatically on the transistor array as the basic cell array arranged on the chip 61 so as to realize the LSI circuit having the required functions.
When the macro cells are arranged automatically on the transistor array, they are placed in rows.
Electrical wiring among the macro cells is executed automatically in the intervals between the rows. The interval is called by a channel region for the electrical wiring.
As described above, the width of the channel is determined by the size of the chip 61. Accordingly, in the layout design for an LSI, it is most important to reduce the number of unrouted nets.
Accordingly, in an automatic placement procedure of the layout design for the macro cells, the wirable macro cell placements having the smallest number of unrouted nets should be determined when an automatic wiring operation is carried out as a following step.
There are some conventional methods for determining the wirable placement.
(1) K. H. khokhani and A. M. Patel, "The Chip Layout Problem-A Placement Procedure", Proc. 14th Design Automation Conference, 1977, pp. 291-297.
(2) A. M. Patel, "A WIRABILITY PLACEMENT ALGORITHM FOR HIERARCHICAL VLSI LAYOUT", Proc IEEE 1984, pp. 344-350.
(3) H. Shiraishi and F. Hirose, "Efficient Placement and Routing Technique for master Slice LSI", Proc. 17th Design Automation Conference, 1980, pp. 458-464.
By these methods, the distribution of electrical wiring is uniform over the entire chip 61, so as to determine wire. Namely, it is determined by the method in which the wiring routes per net (per macro cell), in the layout design of the electrical wiring to be formed on the chip 61, are so predicted that the total capacity of the predicted layout is kept within the predetermined wiring capacity on the chip 61.
For predicting the wiring routes, the Steiner-tree model is used in cited conventional networks (1) and (2). These authors say that the Steiner-tree model reflects an actual wiring layout with the most efficiency of any in the prior art. However, it takes considerable time to obtain the resultant wiring layout by using that model. Namely, when the methods (1) and (2) described above are used for obtaining wiring layouts, considerable time is required.
In addition, these authors, above mentioned, acknowledge that it is difficult to obtain the required wiring layout reflecting the actual wiring layout because only the wiring length on the chip is considered in these methods.
On the other hand, the following work describes a wirable placement that can be obtained by the uniform, distribution of connecting terminals over the chip. See
[4] K. Klein., et al., "A study on Bipolar VLSI Gate-Array Assuming Four Layers of Metal", IEEE. J. of Solid-State Circuits, vol. sc-17, No. 3, Jun. 1982, pp 472-480.
In this method, a correlation between the distribution of the electric wiring and the connecting terminals is considered. A problem from crowded local wiring can be solved by the method. However, this method does not apply sufficiently to a distribution of electrical wiring having a wide or global area.
As described above, in order to obtain a wirable placement within a short time, evaluation functions for the global wiring state, and the local wiring state, and a procedure for efficiently evaluating relationships among these functions, is required. Moreover, a method to efficiently optimize these functions is also required. Because the evaluated functions, such as the distributions of the wiring and connecting terminals described above are not adequate it is not always possible to obtain an optimizing wirable placement within a short time.
There are methods to optimize the relationship among these evaluation functions, for example, those described in work (2).
In work (2), the method to optimize the relationship between the wiring length and the locally crowded wiring is used. On the other hand, it is common to use this method to minimize a difference between each evaluate function and a target value thereof which is preliminarily set per evaluate function.
In the method for optimizing two evaluate functions, the optimizing operation is performed in a predetermined order. Namely, one evaluate function can not be evaluated while the other evaluate function is optimized.
The method for minimizing the difference between the evaluate function and the target thereof cannot obtain the most optimized value (a reoptimized value) because in this method the values of a satisfaction level is set to a predetermined constant value.
In conventional methods, as described above, optimizing operations are performed in order to obtain the wirable placement by using the evaluate functions. However, one cannot fully satisfy the values of the evaluation functions.